n = 1000;
ty = [0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,0,1,1,1,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1,0,0,1,1,1,0,0,1,1,1,1,1,0,1,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,0,1,0,0,1,1,0,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,1,1,0,0,1,0,0,1,1,1,0,1,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,0,1,1,0,0,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,0,0,0,1,1,1,1,1,1,0,1,1,1,1,0,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,0,1,0,0,1,1,1,1,1,1,0,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0,1,0,1,0,1,0,1,1,0,1,1,0,1,0,1,1,1,1,1,0,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,0,0,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,0,1,0,0,1,1,1,0,1,0,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,1,1,0,1,0,0,1,1,1,1,0,1,1,0,1,1,1,1,0,1,0,1,0,1,1,0,0,1,0,1,0,0,0,0,1,1,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,0,0,1,0,1,1,1,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,0,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1,0,0,1,0,1,1,1,0,0,0,0,1,1,1,1,1,0,1,1,1,0,0,1,0,1,1,0,1,1,1,1,1,0,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0,1,1,0,0,1,0,1,1,1,0,1,0,1,1,1,0,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,0,1,0,0,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,0,1,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,0,1,0,0,0,1,0,1,1,1,1,1,0,1,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1,0,1,1,0,1,1,1,0,1,0,0,1,1,1,0,0,0,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,0,1,1,1,1,1,0,0,1,1,0,1,1,0,1,1,0,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,0,1,1,0,0,1,1,0,0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,1,1,1,0,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,0,1,0,1,1,0,0,1,0,0,0,1,1,1,1,0,0,1];
price = [315,703,590,78,545,583,378,198,492,30,295,212,558,267,192,522,160,39,212,369,186,867,173,149,59,140,160,267,29,207,269,861,493,521,832,148,291,291,345,171,398,80,172,765,466,472,502,70,15,325,468,451,354,122,423,149,207,792,840,187,224,117,99,141,380,97,290,80,326,90,275,96,708,677,973,554,608,476,113,351,604,948,264,12,130,13,2,322,435,359,643,360,323,923,508,9,461,41,554,471,603,114,633,255,558,57,2,3,738,871,2,2,3,779,1,2,403,93,65,121,714,78,150,148,58,40,41,327,76,234,385,153,16,557,422,397,211,237,279,114,8,318,409,236,221,163,366,10,143,101,526,225,505,465,483,965,753,413,14,121,832,559,465,439,925,842,201,919,302,341,302,16,16,2,28,203,279,406,74,138,272,226,109,269,390,496,352,352,489,431,39,362,118,963,11,227,100,115,209,113,127,116,591,3,859,799,78,188,194,15,204,127,366,222,150,356,710,354,603,387,757,311,307,227,314,550,42,371,95,279,14,957,507,107,194,115,252,88,87,730,41,338,580,547,507,472,349,341,645,530,26,163,377,406,152,751,542,311,517,617,617,184,539,643,805,396,481,402,294,128,592,469,551,592,620,316,961,114,125,234,317,156,126,109,186,22,854,176,193,261,192,810,166,94,171,22,119,127,34,39,62,33,365,99,189,511,401,770,231,32,208,314,235,277,209,594,412,51,225,306,139,620,564,48,63,103,334,184,100,132,71,168,284,157,642,303,500,166,525,914,419,379,554,36,148,597,800,713,410,553,496,546,363,677,680,497,353,425,542,301,261,87,215,221,382,16,212,84,180,31,31,58,12,29,649,60,20,40,58,34,33,23,16,352,35,26,28,7,56,990,445,27,38,245,399,71,369,180,471,49,313,350,356,350,825,533,309,861,484,706,121,764,756,320,224,66,7,41,606,27,8,721,715,21,34,34,43,773,21,51,776,11,36,41,3,440,36,768,2,302,590,34,981,421,57,976,639,132,633,142,1000,45,248,173,56,297,210,995,599,27,195,117,14,411,267,54,62,184,409,212,136,17,74,48,88,92,148,31,118,56,472,754,698,133,507,830,166,369,590,347,325,351,152,190,211,73,457,243,258,313,334,419,223,316,371,395,212,122,117,41,309,386,313,24,50,739,401,396,376,303,211,526,667,258,108,853,95,363,496,461,450,93,293,168,484,387,165,61,86,378,13,73,56,696,523,138,93,96,145,137,26,38,61,71,93,74,14,670,1,497,989,398,958,483,266,939,983,595,886,279,229,911,768,362,338,158,230,682,238,44,331,172,260,367,216,159,260,445,292,310,323,68,262,338,479,320,108,404,574,400,360,481,347,793,70,93,344,468,437,99,627,483,85,678,505,606,553,432,107,672,212,175,89,131,75,3,113,69,99,59,191,724,99,352,86,123,669,119,186,178,4,115,594,175,127,397,16,456,998,282,503,422,55,626,289,337,258,157,31,429,512,246,93,324,36,747,292,241,118,76,92,213,42,15,40,517,47,358,615,146,644,200,436,460,539,159,709,618,342,400,924,21,196,490,713,417,484,257,400,124,9,675,99,104,286,793,213,93,253,334,93,470,961,247,333,234,313,455,83,851,715,757,83,60,549,359,180,492,448,484,368,990,554,653,746,836,979,218,520,500,835,546,181,705,64,20,24,51,2,64,565,101,24,31,386,106,579,69,526,71,285,523,284,525,254,260,122,311,320,12,471,314,726,4,209,340,384,497,424,273,555,561,515,209,561,278,891,40,17,91,15,251,999,89,454,155,45,462,424,78,350,604,99,410,175,149,386,226,507,526,199,148,107,698,248,387,228,955,291,135,222,283,277,722,235,169,246,483,266,464,784,6,61,94,234,400,171,592,781,511,65,393,650,740,112,81,123,199,669,591,881,36,33,205,36,103,226,238,281,351,212,300,472,809,317,370,542,377,488,313,35,480,40,378,72,234,583,587,892,588,602,689,83,113,101,81,106,22,139,165,120,645,751,370,103,15,40,56,108,116,156,129,394,446,289,329,543,326,550,12,284,661,637,136,388,68,862,434,147,515,571,23,307,784,466,154,393,261,79,716,278,501,737,494,167,17,227,237,396,285,310,318,937,263,220,264,234,177,194,402,248,454,544,263,91,263,287,242,9,171,101,252,416,75,83,20,913,405,498,423,386,54,285,139,182,395,135,185,217,183,233,193,530,219,983,264,104,887,416,604,184,527,106,69,151,117,42,740,289,254];
time = [307,312,325,326,333,334,338,341,343,344,345,346,348,349,350,351,360,361,366,382,394,395,396,397,399,400,401,402,403,404,589,612,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,667,1626,1639,1655,1668,1669,1670,1698,1727,1730,1735,1736,1738,1740,1741,1742,1909,1935,1937,1938,1939,1940,1941,1942,1943,1944,1945,1946,1947,1948,1949,1950,1951,1952,1953,1976,1988,2015,2017,2030,2062,2068,2069,2072,2868,2885,2896,2900,2901,2902,2904,2906,2907,2908,2909,2910,2911,2912,2934,2946,2967,2971,2972,2973,2974,2975,2976,2977,2978,2979,2985,3004,3014,3015,3016,3017,3019,3020,3021,3022,3023,3038,3051,3055,3073,3077,3078,3082,3104,3126,3130,3133,3135,3136,3137,3138,3139,3140,3141,3142,3143,3144,3145,3146,3147,3148,3302,3333,3335,3337,3338,3339,3340,3341,3343,3344,3345,3346,3531,3538,3568,3574,3575,3606,3637,3638,3649,3657,3682,3690,3691,3694,3695,3697,3698,3699,3700,3701,3724,3763,3764,3765,3766,3768,4024,4028,4041,4052,4053,4054,4055,4056,4057,4058,4059,4060,4061,4062,4063,4064,4065,4066,4067,4068,4099,4122,4123,4128,4131,4132,4133,4134,4135,4136,4137,4138,4139,4140,4141,4142,4143,4397,4436,4437,4438,4684,4689,4699,4723,4724,4725,4727,4728,4754,4756,4758,4782,4788,4793,4794,4795,4796,4797,4798,4835,4857,4862,4869,4870,4871,4872,4873,4874,4875,4876,4877,4878,4879,5323,5350,5353,5354,5356,5357,5360,5361,5363,5364,5365,5366,5389,5416,5420,5422,5423,5424,5425,5426,5427,5428,5429,5430,5431,5432,5433,5737,5767,5775,5776,5781,5784,5826,5827,5828,6427,6460,6470,6471,6641,6658,6668,6670,6672,6675,6677,6680,6681,6682,6683,6684,6685,6827,6865,6866,6867,6868,6869,6870,6871,6909,6941,6944,6946,6949,6950,6951,6952,6953,7715,7720,7723,7742,7748,7750,7754,7755,7756,7757,7758,7759,7766,7793,7809,7810,7826,7837,7847,7855,7860,7864,7866,7867,7869,7870,8064,8086,8091,8095,8100,8102,8105,8324,8351,8352,8359,8362,8364,8365,8366,8367,8368,8404,8431,8434,8436,8438,8440,8441,8442,8443,8444,8445,8446,8447,8448,8487,8492,8505,8514,8523,8524,8526,8529,8530,8758,8780,8786,8789,8790,8791,8792,8793,8794,8795,8796,8797,8798,8799,8800,8801,8802,8825,8840,8844,8847,8854,8855,8856,8857,8858,8859,8860,8861,8862,8863,8864,8865,8866,8867,8868,8869,9094,9096,9105,9114,9602,9640,9644,9646,9903,9931,9941,9942,9943,9944,9945,9946,9947,10936,10958,10964,10968,10970,10971,10973,10974,10975,10976,10977,10978,10979,10980,10985,11022,11038,11058,11059,11072,11075,11080,11081,11082,11091,11108,11116,11124,11128,11131,11132,11134,11135,11729,11751,11753,11760,11761,11762,11763,11764,11765,11766,11767,11768,11769,11770,11771,11772,11773,11808,11829,11832,11840,11845,11848,11849,11850,11851,11852,12826,12834,13339,13347,13362,13369,13376,13419,13436,13443,13448,13450,13451,13452,13453,13454,13455,13456,13457,13458,13459,13460,13461,13462,13463,14336,14363,14365,14366,14367,14368,14369,14370,14371,14372,14373,14374,14375,14376,14377,14378,14379,14380,14893,14913,14922,14924,14925,14926,14927,14928,14929,14930,14931,14932,14933,14934,14935,14936,14937,14977,14991,14995,15001,15007,15012,15013,15014,15018,15019,15020,15021,15429,15441,15455,15457,15458,15459,15460,15461,15462,15463,15464,15465,15466,15467,15468,15469,15470,15471,15472,15473,15739,15756,15773,15776,15777,15778,15780,15781,15782,15783,15811,15846,15848,15851,15852,15853,15854,15855,15892,15918,15919,15921,15923,15924,15925,15926,15927,15928,15929,15930,15931,15932,15933,15934,15935,15936,15943,15984,15987,16018,16044,16051,16052,16055,16056,16057,16058,16059,16060,16061,16062,16075,16114,16551,16565,16590,16591,16592,16593,16594,16595,16616,16632,16637,16652,16654,16656,16657,16660,17447,17459,17471,17475,17481,17487,18274,18304,18306,18307,18308,18310,18311,18312,18313,18314,18315,18316,18317,18318,18356,18366,18368,18371,18375,18382,18387,18388,18389,18390,18391,18392,18393,18394,18395,18396,18397,18398,18399,18400,18429,18430,18470,18471,18472,19400,19429,19435,19438,19478,19487,19499,19514,19517,19519,19520,19521,19522,19523,19524,19525,19526,19527,19528,19529,19530,19531,19560,19577,19583,19590,19592,19594,19595,19596,19597,19598,19599,19600,19601,19602,19603,19604,19936,19938,19972,19973,19974,19975,19976,19977,19978,19979,19980,20840,20854,20856,20860,20869,20871,20875,20876,20877,20878,20879,20880,20881,20882,20883,20884,20906,20938,21586,21628,22339,22344,22353,22361,22368,22369,22371,22372,22373,22374,22375,22376,22377,22378,22379,22380,22381,22382,22383,22485,22509,22513,22514,22516,22518,22519,22520,22521,22522,22523,22524,22525,22526,22527,22528,22529,22761,22780,22791,22801,22803,22804,22805,23452,24200,24205,24206,24227,24230,24231,24232,24233,24235,24236,24237,24238,24239,24240,24241,24242,24243,24244,24924,24960,24962,24963,24964,24965,24966,24967,24968,25944,25984,26012,26037,26039,26041,26043,26044,26045,26046,26047,26048,26049,26050,26051,26052,26053,26054,26055,26056,26068,26071,26078,26096,26097,26098,26099,26100,26101,26102,26103,26104,26105,26106,26107,26108,26109,26110,26111,26112,26874,26893,26913,26923,26925,26926,26927,26929,26931,26932,26933,26934,26935,26936,26937,27781,27797,27799,27812,27813,27814,27815,27816,27817,27818,27819,27820,27821,27822,27823,27824,27825,28626,28648,28653,28658,28661,28663,28667,28668,28669,28670,28680,28692,28705,28714,28739,28743,28746,28749,28750,28751,28752,28753,28754,28755,28756,28757,28758,28778,28784,28805,28808,28812,28813,28814,28815,28816,28817,28818,28819,28820,28821,28822,28859,28903,28934,28938,28939,28941,28942,28943,28944,28945,28946,28947,28967,29002,29010,29011,29046,29066,29080,29083,29084,29088,29503,29541];